import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 84. Largest Rectangle in Histogram 柱状图中最大矩形
 * https://leetcode.com/problems/largest-rectangle-in-histogram/
 */
class LargestRectangleInHistogram {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Deque<Integer> st = new ArrayDeque<>();
        // 在栈中只有一个数的时候，栈顶的「下面那个数」是 -1，对应 left[i] = -1 的情况
        st.push(-1);
        int ans = 0;
        for(int right = 0; right <= n; right++){
            int h = right < n ? heights[right] : -1;
            while(st.size() > 1 && h <= heights[st.peek()]){
                int i = st.pop();
                int left = st.peek();
                ans = Math.max(ans, heights[i] * (right - left - 1));
            }
            st.push(right);
        }
        return ans;
    }
}